1. Field of the Invention
The present invention relates to a graphic form recognizer for use as an input unit of a computer system or the like for recognizing line graphic forms, and more particularly, to a device for recognizing handwritten graphic forms created by using a digitizer or a tablet.
2. Description of the Related Art
Among graphic form recognizers used for inputting line graphic forms to a computer system, etc. are a drawing reader which reads drawings by using an optical means and an interactive drawing input device using a digitizer or a tablet. In general, these graphic form recognizers recognize a graphic form by dividing a line constituting the graphic form into sections each composed of basic line segments such as a straight line and a circular arc and specifying position of points including a flection point and an inflection point (hereinafter, referred to as feature points) which divide the graphic form and a kind of a line segment (line kind) constituting the section to calculate consistency with predetermined dictionary data.
Such graphic form recognition requires, on condition that a line graphic form is constituted by a sequence of successive points, extraction of feature points from the respective points constituting the graphic form and determination of a line kind of a section sandwiched between the feature points.
Conventionally, the following two kinds of means are mainly used to determine whether a point on a graphic form is a feature point or not.
A first means is to extract sample points, at a predetermined distance, from points constituting a graphic form made up of a sequence of points and regard, as a feature point, a section where an elevation angle or a rate of change of an elevation angle is larger than a predetermined value, which elevation angle is formed by two line segments created by Joining three sample points located at the interval of n points. Such means is recited in, for example, Patent Publication No. H4-62107 and Patent Laying-Open No. S63-24473.
The conventional graphic form recognizer reads a graphic form by using an optical means and the like, makes a sequence of points out of the graphic form and extracts sample points from among point data of the graphic form of a sequence of points. Then, the recognizer extracts feature points from the sample points and determines whether a line segment of a section between the feature points is a straight line or a curve. The recognizer then recognizes a shape of the graphic form based on a position of the feature point and a line kind to display the recognition results on a display etc.
Herein, the conventional graphic recognizer described above determines whether point data of each sample point is regarded as a feature point or not based on an elevation angle formed by two line segments created by joining three sample points located at the interval of n points. More specifically, with n=1, an elevation angle is formed by two line segments created by joining three adjacent sample points. The elevation angle may be computed by performing calculations of an arithmetical mean of elevation angles at a predetermined number of points, that is, by smoothing process according to the moving average method. In finding a feature point, determination that a sample point in question is a feature point or not can be made when an obtained elevation angle is larger than a predetermined value or when a difference between two elevation angles adjacent to each other is larger than a predetermined value.
A function of the above-described adjacent elevation angle represented on a coordinate plane is as shown in FIG. 11A, with a value of an adjacent angle as the ordinate and a distance as the abscissa. In the figure, steps and peaks can be used for the determination of feature points and a gradient of a line segment for the determination of a kind of line.
A second means for determining feature points is to divide a graphic form according to predetermined rules, approximate the graphic form by broken lines by joining the divisional sections by straight lines, determine whether each division point, which is a connection between straight lines, is an angle, or a portion to be united into a single curve or a single straight line based on a value of an elevation angle formed by two line segments and take, as a feature point, a division point remaining to the last without integration into a single curve or a straight line as a point to form an angle. The foregoing means is recited, for example, in Japanese Patent Laying-Open No. S58-62767 and Japanese Patent Laying-Open No. H4-160687.
Japanese Patent Laying-Open No. S58-62767 recites a method of dividing a graphic form such that a distance between a straight line formed by joining two arbitrary points and a sequence of points in a section sandwiched between the two points is not larger than a fixed value. Recited in Japanese Patent Laying-Open No. H4-160687 is a method of determining whether or not to divide a section based on the dimensions of a region surrounded by a straight line created by joining two arbitrary points on the graphic form and by a sequence of points of the section.
This conventional graphic form recognizer extracts a maximum value of a distance between a point sequence between two predetermined reference points and a straight line linking the reference points, and data of a point positioned at the largest distance from the straight line joining the reference points. Then, when the maximum value of a distance between the point of the sequence and the straight line is larger than a predetermined value, the extracted point data is stored as a reference point. With respect to a graphic form approximated by broken lines in this manner, determination is made whether a division point, which is a connection between two adjacent straight lines, is an angle, or a portion to be united into a single curve or a single straight line based on a value of the center elevation angle to execute integration processing of the section when necessary. Then, point data of a division point remaining to the last is output as a feature point.
As described in the foregoing, recognition of a graphic form by using a graphic form recognizer also requires determination of a kind of a line of a section sandwiched between feature points. One of conventional manners for such determination is finding a total curvature of a graphic form by executing smoothing processing with respect to an elevation angle formed by line segments joining each point of a point sequence according to the moving average method and determining a kind of a line of a section in question based on the total curvature, which is recited in, for example, Japanese Patent Laying-Open No. S63-276182. In addition to implementing the above-described line kind determination means, the graphic form approximation device recited in the article reduces roundness of a graphic form generated during the averaging process by correcting the vicinity of an inflection point and that of a connection between a straight line and a circular arc. The article also discloses an arrangement to realize approximation of a graphic form. In combination with a means for calculating consistency of a feature point and a kind of a line segment with dictionary data, this arrangement will be allowed to carry out graphic form recognition.
This conventional graphic form recognizer finds an angle formed by a direction joining two successive points on an input graphic form and a fixed reference direction (hereinafter, referred to as a total curvature) and determines a line kind based on a total curvature corresponding to each sample point between the successive feature points.
More specifically, smoothing processing according to the moving average method is executed by inputting point data of a sample point to find a total curvature (.theta.) at each sample point and computing, with respect to each sample point, an arithmetical mean of total curvatures (.theta.) of a n number of preceding and a n number of succeeding points to the sample point. Then, an average gradient of the total curvature E (.theta.) of each sample point between two feature points is obtained to make determination that a section sandwiched between the feature points is a circular arc when the absolute value of the average gradient of the total curvature is within a fixed range and that the section sandwiched between the feature points is a straight line when the absolute value is approximately 0.
Illustration of the function of a total curvature E (.theta.) expressed on a coordinate plane is FIG. 12A, wherein the ordinate represents the total curvature and the abscissa represents a distance. Depending on a gradient of a line segment shown in the figure, a line kind can be determined.
The foregoing graphic form recognizer may cause random noise or burst noise when in inputting a graphic form, which leads to reduction of input precision. An optical reader used for inputting a graphic form generates random noise referred to as edge noise when binarizing an analog waveform output from a CCD sensor. Such device for reading a handwritten locus by a tablet etc. also generates random noise including a shake of a hand. A built-in-display tablet in which an LCD and a tablet are integrated generates a burst noise due to electro-magnetic wave emitted from the LCD and from other causes.
FIG. 8 is a diagram showing an example of output results, including random noise and burst noise, of a graphic form input unit 11.
The above-described conventional graphic form recognizer removes effects of these noises by adjusting various parameters according to a state of the noises.
For example, when in extracting sample points from an input graphic form made of a sequence of points, the adjustment is made such as by thinning out points of the sequence on a basis of a length enough for excluding effects of noise generated at the time of inputting a graphic form, adjusting the number of points between sample points at the time of computing adjacent elevation angles or a number of points for use in the moving average method, and adjusting the number of points necessary in the moving average method for computing a total curvature.
These conventional methods may not fully remove the effects of noise because of difficulty in adjustment.
In the adjustment by thinning-out processing, for example, too large a thinning-out distance, aimed at increasing a noise removal capability, results in thinning out points in the neighborhood of a target point to be extracted as a feature point. As a result, the feature point will be displaced to prevent creation of a fair copy whose form is corrected or lead to an error in the number of feature points and misidentification of a line kind. In addition, the number of sample points which can be used for line kind determination is reduced, so that enough reliability of line kind determination can not be achieved.
In other words, at the time of extracting sample points, when thinning-out is executed on various conditions provided for removing only random noise as shown in FIG. 9, a thinning-out determination unit can not remove burst noise but misidentifies the position of the noise as a feature point.
On the other hand, on various conditions set for removing burst noise as well as random noise as shown in FIG. 10, there is a case where a point in the vicinity of a sample point to be initially regarded as a feature point is thinned out, causing omission of the extraction of feature points or misidentification of a line kind.
In the adjustment according to the moving average method, too large a number of points for use in smoothing processing aimed at increasing a noise removing capability leads to excessive smoothing, resulting in misidentifying curves other than circular arcs as circular arcs or making determination of a kind of short lines difficult.
In other words, with little noise, an elevation angle function and a total curvature function obtained by the moving average method will be expressed by a level straight line, or a slanting straight line or a curve according to a kind of a line of an input graphic form, for example, as shown in FIGS. 11A and 12A, while with too large burst noise etc. to be removed, a relationship between a kind of a line of the input graphic form and characteristics of the elevation angle function will be difficult to extract or be lost.
The adjustment in the number of points between sample points necessary for computation of adjacent elevation angles is of little effect for removing burst noise. More specifically, when a center sample point is a burst noise, an elevation angle becomes unduly large, so that the part is often misidentified as a feature point. In addition, too large a number of points between sample points set to increase a random noise removing capability results in that a curve portion with a large total curvature will have an unduly large elevation angle. As a result, there occurs a case where a feature point is found at a curve portion.
A graphic form recognizer which determines feature points by approximating a graphic form by broken lines, processing a division point in question based on a value of an elevation angle formed by two line segments and taking the remaining division point as a feature point is relatively unsusceptible to such effect of random noise as described above. In particular, burst noise is of little effect when in using, as a guide to determination for division, an area of a region surrounded by a straight line joining reference points and a sequence of points sandwiched by the reference points.
While the above method causes no problem with a graphic form made up of straight lines only, it does with a graphic form including a curve portion because the curve portion is also approximated by broken lines made up of several straight lines.
More specifically, in the approximation of a curve portion by broken lines, each elevation angle of a broken line might vary even in the same circular arc because of variation in division according to threshold values. Integration processing using such elevation angles and changes of the same leads to misidentification.
In addition, an unnecessarily large number of divisions of a curve portion sacrifices a processing speed.